#include <stdlib.h>
#include <stdio.h>
typedef struct node
{
    int data;          // 数据域
    struct node *prev; // 指针域
    struct node *next; // 指针域
} Node;
typedef struct list
{
    Node *header; // 头指针
    Node *tail;   // 尾指针
    int size;     // 大小
} List;

void init(List *list);
void add(List *list, int data);
void show(List *list);
Node *get(List *list, int index);
void insert(List *list, int index, int data);
void insert2(Node *node, int n);
void del(List *list, int index);

int main()
{
    List *list = malloc(sizeof(List));

    init(list);
    show(list);
    // int a[] = {100,200,300,400};
    // init_by_arry(list , a, );
    add(list, 100);
    add(list, 200);
    add(list, 300);
    add(list, 400);
    show(list);

    Node *n = get(list, 2);
    printf("%d ", n->data);
    // insert2(n,999);
    insert(list, 2, 888);
    show(list);

    return 0;
}
void init(List *list)
{
    list->header = malloc(sizeof(Node));
    list->tail = malloc(sizeof(Node));
    // 尾指针指向头指针，链表为空
    list->tail = list->header;
    list->header->next = NULL;
    list->size = 0;
}
void add(List *list, int data)
{
    // 创建新节点
    Node *node = malloc(sizeof(Node));
    node->data = data;
    // 新节点的前驱是尾指针
    node->prev = list->tail;
    node->next = NULL;
    // 新节点成为最后一个节点（尾指针指向的节点）的后继
    list->tail->next = node;
    list->tail = node;
    list->size++;
}
void show(List *list)
{
    printf("链表大小：%d\n", list->size);
    printf("遍历:");
    // 第一个节点
    Node *cur = list->header->next;
    while (cur != NULL)
    {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}
// 基于索引访问链表中的元素 O(n)
Node *get(List *list, int index)
{
    // TODO 优化
    Node *node = list->header;
    for (int i = 0; i <= index; i++)
    {
        node = node->next;
    }
    return node;
}
void insert(List *list, int index, int n)
{
    Node *p = get(list, index - 1);

    Node *node = malloc(sizeof(Node));
    node->data = n;
    node->next = p->next;
    node->prev = p;
    p->next->prev = node;
    p->next = node;

    list->size++;
}
void insert2(Node *m, int n)
{
    Node *p = m;

    Node *node = malloc(sizeof(Node));
    node->data = n;
    node->next = p->next;
    node->prev = p;
    // 下面两个不能换位
    p->next->prev = node;
    p->next = node;
}
void del(List *list, int index)
{
    // Node *p = get(list, index - 1);

    // Node *n = p->next;
    // p->next->next->prev = p;
    // p->next = p->next->next;
    // free(n);

    // 要删除的节点
    Node *n = get(list, index);
    Node *p = n->prev;

    n->next->prev = p;
    p->next = n->next;
    free(n);

    list->size--;
}